The present invention relates to electronic design automation (EDA), and more particularly, to techniques for decomposing a layout of an integrated circuit (IC) into a multitude of masks of a multiple-patterning lithography process.
As the feature size of semiconductor technology continues shrinking, multiple patterning lithography (MPL) has been considered one of solution candidates to overcome the resolution limit of conventional optical lithography, along with four next generation lithography techniques—extreme ultraviolet lithography, directed self-assembly, nanoimprint lithography, and electron beam lithography. MPL may extend 193 nm immersion lithography to sub-14 nm nodes by performing a series of exposure/etching steps to pattern a layer of the IC using a multitude of masks derived from a layout represented by a set of polygonal features to be printed on the layer. MPL thereby improves the effective pitch and the lithography resolution compared to a lithography process using just a single mask. One challenge of MPL is layout decomposition, where a layout is divided into several masks.
MPL includes double patterning lithography (DPL), triple patterning lithography (TPL), quadruple patterning lithography (QPL), and so on. Thus far, existing works focus on only the basic coloring rule, i.e. the same color spacing constraint cs, and model this version of multiple patterning layout decomposition (MPLD) as a graph coloring problem on a conflict graph. Even this version of MPLD is difficult because graph coloring on a general graph is computationally hard. The simplest form of MPL is DPL. The double patterning layout decomposition problem corresponds to a two-coloring problem. A conflict graph without odd cycles is two-colorable. Hence, testing two-colorability and two-coloring a conflict graph can be done in linear time by breadth-first search techniques.
TPL, which is a natural extension of DPL, decomposes a layout into three masks instead of two and thus can handle more dense and complex layouts with fewer stitches and conflicts. However, triple patterning layout decomposition turns out to be a hard problem because testing three-colorability of a graph and three-coloring a three-colorable graph are both NP-complete. Compared with TPL, QPL adds one more mask, which is modeled as a four-coloring problem. As more masks are used as technology advances, the conflict graph becomes denser, and as more complex coloring rules are introduced, thus MPLD becomes even more challenging.
Recently, there have been extensive researches on MLB decomposition described using different numbers of masks. For DPL that uses two masks, a min-cut-based polynomial time algorithm has been presented which delivers the most up-to-date results. For TPL and QPL, prior works mainly fall into two categories: mathematical programming and fast heuristics. The mathematical programming approach, e.g., integer linear programming (ILP) and semidefinite programming (SDP), seeks optimality but may consume long computer runtime that may require speedup techniques. Fast heuristics, e.g., lookup table, pairwise coloring, and modified independent set techniques, are usually efficient but may lose some solution quality and produce some false coloring conflicts. So far, all of these methods are developed to resolve graph coloring corresponding to complying with a single basic coloring rule and model multiple patterning layout decomposition as a graph coloring problem. However, multiple patterning layout decomposition with more complex coloring rules, such as when more than one coloring rule is required, is not just a conventional graph coloring problem, and thus these methods cannot easily be extended to handle the complex coloring rules.
Accordingly, there is a need to be able to decompose a layout for MLP that comprehends complex coloring rules using triple or higher patterning lithography technology.